package com.bigshen.algorithm.dBinarySearch.solution05CutWood;

public class CutWood {


    /**
     * 切木头
     *
     * 给定N块不同长度的木头，比如213,225,456,731 四块，
     * 现在需要从中切出N块等长的木头，切的长度尽量长，比如需要6块。
     *
     * // 二分法：
     * 首先找出最长的一块木头，然后二分法找出中位值，以这个长度去尝试切木头，
     *   如果切出的块数大于等于需要的块数，表明可以用更长的长度去切；
     *   如果切出的块数不够，用更短的长度去切；
     *
     * @param array  不同长度木头数组
     * @param pieces  需要的块数
     * @return 切的木头长度
     */
    public int cutWood(int[] array, int pieces) {

        if (null == array || array.length == 0) {
            return 0;
        }

        // 最大长度木头
        int maxLength = getMax(array);

        int start = 1;
        int end = maxLength;

        while (start + 1 < end) {
            int mid = start + (end-start)/2;
            // 尝试以中位值去切木头，可以切几块
            int currentPiece = getPieces(array, mid);
            if (currentPiece >= pieces) {
                // 切出的块数超过了需要的，尝试切更长  start -->
                start = mid;
            } else {
                // 不能切出足够的块数， 尝试切更短  <-- end
                end = mid;
            }
        }

        if (getPieces(array, end) >= pieces) {
            return end;
        }

        if (getPieces(array, start) >= pieces) {
            return start;
        }

        return -1;

    }

    private int getPieces(int[] array, int length) {
        int pieces = 0;
        for (int element : array) {
            pieces += element/length;
        }
        return pieces;
    }

    private int getMax(int[] array) {
        int max = 0;
        for (int len : array) {
            max = (max > len ? max : len);
        }
        return max;
    }

    public static void main(String[] args) {

        int[] array = {213,331,532,137,1};
        int pieces = 6;

        int maxLen = new Solution().cutWood(array, pieces);

        System.out.println(maxLen);
    }

}
